package tree.heap.arrayUse0IndexHeap;

/**
 * 功能描述: 大顶堆: 堆顶元素最大 : 大顶堆与小顶堆 无非就是改变比较规则:不同的比价器
 * 2024/05/27
 * <p>
 * ZhangYi
 */
public class MaxTopHeapArrayUtils {

    public static void main(String[] args){
        int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};

        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }

        int heapSize = arr.length;
        swapValue(arr,0,--heapSize);

        while (heapSize>0){
            heapfiy(arr,0,heapSize);
            swapValue(arr,0,--heapSize);
        }
        System.out.println(1);
    }

    /**
     * 功能描述: 堆化,弹出元素后,交换, 将堆中的元素调整为大根堆, 使其维持大跟堆
     *
     * @param arr      arr
     * @param index    索引
     * @param heapSize 堆大小
     */
    private static void heapfiy(int[] arr,
                                int index,
                                int heapSize) {
        int leftIndex = (index<<1)|1 ;
        while (leftIndex < heapSize){
            int largestIndex = leftIndex +1 < heapSize && arr[leftIndex+1] > arr[leftIndex] ? leftIndex +1 : leftIndex;

            largestIndex = arr[index] > arr[largestIndex]? index : largestIndex;

            if (largestIndex == index){
                return;
            }

            swapValue(arr,index,largestIndex);
            index = largestIndex;
            leftIndex = (index<<1)|1 ; // 更新index 和 leftIndex 的值
        }

    }

    /**
     * 功能描述: 插入元素, 插入元素后, 调整堆, 使其维持大根堆,最大值靠近索引 0 位置
     *
     * @param arr   arr
     * @param index 索引
     */
    private static void heapInsert(int[] arr,
                                   int index) {
        // 大顶堆, 父节点的值大于子节点的值
        while (arr[index]> arr[(index-1)/2]){
            swapValue(arr,index,(index-1)/2);
            index = (index -1)/2;
        }
    }

    private static void swapValue(int[] arr,
                                  int index,
                                  int index2) {
        int temp = arr[index];
        arr[index] = arr[index2];
        arr[index2] = temp;
    }
}
